package com.hy;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:单词最大长度乘积
 * author: Mr.Du
 * Date: 2022/11/21
 * Time: 16:58
 */
public class MaxProduct {
    
    public static void main(String[] args) {
        System.out.println('a' - 97);
        MaxProduct maxProduct = new MaxProduct();
        int res = maxProduct.maxProduct1(new String[]{"abcw", "baz", "foo", "bar", "fxyz", "abcdef"});
        System.out.println(res);
        res = maxProduct.maxProduct(new String[]{"abc", "baz", "foo", "bar", "fxyz", "abcdef"});
        System.out.println(res);
    }
    
    /**
     * 位运算
     * 将每个单词的字符换成二进制，如："abc" ---> 0111   "xyz" ---> 11 1000 0000 0000 0000 0000 0000
     * 如果两个字符串互相不含有相同字符，它们 & 操作就是0
     * @param words
     * @return
     */
    public int maxProduct(String[] words) {
        int[] nums = new int[words.length];
        int res = 0;
        for(int i = 0;i < words.length;i++){
            String s = words[i];
            for(int j = 0;j < s.length();j++){
                nums[i] |= (1 << (s.charAt(j) - 'a'));
            }
        }
        System.out.println(Arrays.toString(nums));
        for(int i = 0;i < words.length;i++){
            for(int j = i + 1;j < words.length;j++){
                if((nums[i] & nums[j]) == 0){
                    res = Math.max(res,words[i].length() * words[j].length());
                }
            }
        }
        return res;
    }
    
    /**
     * 暴力解决
     * @param words
     * @return
     */
    public int maxProduct1(String[] words) {
        int[] nums = new int[26];
        int res = 0;
        for(int i = 0;i < words.length;i++){
            // 初始化数据
            isExist(nums,words[i],false);
            for(int j = i + 1;j < words.length;j++){
                // 如果不存在，说明i和j的单词没有重复部分，计算结果
                if(isExist(nums,words[j],true)){
                    res = Math.max(words[i].length() * words[j].length(), res);
                }
            }
            Arrays.fill(nums,0);
        }
        return res;
    }
    
    public boolean isExist(int[] nums,String s,boolean flag){
        for(int i = 0;i < s.length();i++){
            if(flag){
                if(nums[s.charAt(i) - 'a'] != 0){
                    return false;
                }
            }else{
                nums[s.charAt(i) - 'a']++;
            }
            
        }
        return true;
    }
}
